/* 写出深度优先遍历的非递归算法 */

#include <iostream>
#include "algraph.h"
using namespace std;

// 深度优先遍历
void DFS1(ALGraph *G, int v)
{
  // 访问标记，初始均未被访问
  int visit[maxsize];
  for (int i = 0; i < G->numver; ++i)
    visit[i] = 0;
  
  // 辅助栈
  int stack[maxsize];
  int top = -1;
  
  // 访问开始结点
  cout << v << " ";
  visit[v] = 1;
  
  // 结点进栈
  stack[++top] = v;
  
  // 如果栈不为空
  while (top != -1)
  {
    // 访问栈顶结点
    int k = stack[top];
    
    // 找到邻接结点
    ArcNode *p = G->adjlist[k].firstarc;
    
    // 找未被访问过的邻接结点
    while (p != NULL && visit[p->adjvex] == 1)
      p = p->nextarc; 
    
    // 邻接结点均被访问过
    if (p == NULL)
      --top; // 出栈
    
    // 有邻接结点未被访问
    else
    {
      // 访问
      cout << p->adjvex << " ";
      visit[p->adjvex] = 1;
      
      // 邻接结点入栈
      stack[++top] = p->adjvex;
    }
  }
}
int main()
{
  // 创建图 -- 邻接表
  ALGraph *G = create_algraph(4, 4);
  
  // 深度优先遍历，2为开始结点
  DFS1(G, 2);
  return 0;
}